\chapter{Background}
This chapter explains about the traditional compilation model, the Davidson Fraser model and how GCC differs from the traditional 
model and the effect of this on the retargeting process of GCC. This also introduces some basic concepts needed to understand
GCC's machine description files and the RTL expressions used in them.

\section{Aho Ullman Model}
The Traditional Aho Ullman Model of compilation\cite{Aho} advocates grouping the various phases of compilation into three logical units,
the front end, the optimizer and the back end as seen in figure \ref{fig:FigureAho}


\begin{figure}[htb!]
\centering%
\includegraphics[scale = 0.5]{Aho.pdf}
\caption{Aho Ullman Model of Compilation}
\label{fig:FigureAho}
\end{figure}

		    The front end, converts the source language into an intermediate representation which is both machine-independent and language 
independent. The intermediate language, can be considered as a language for an abstract machine. The optimizer, works on the 
intermediate language and improves on it. The back end, also known as the code generation phase, does the work of instruction 
selection, instruction scheduling, register allocation. The front end isolates the source language specific issues while the 
back end isolates the machine dependent features from the rest of the compiler. This is supposed to make the process of retargeting such a compiler 
relatively easy. The optimizer which works on the language and machine-independent intermediate representation can be reused
across any combinations of source language and target machine. 

				  In this model, to retarget the compiler to a new machine, only the back end has to be rewritten. To be more specific, the instruction
selection part of the back end has to be rewritten. The instruction selector does a pattern matching over the compiler's
intermediate representation and executes a code fragment associated with this pattern, which produces the assembly code. So a 
knowledge of the compiler's intermediate representation and the target machine's instruction set is needed to write this new
instruction selector. In this model, the back end has to be written very carefully, since the target code generated by it, determines the 
efficiency of the source program as no further optimizations are done over it.

\section{Davidson Fraser Model}

The Davidson Fraser Model\cite{Davidson}, pitched for a compiler that optimizes the code generated by the code generator. 
\begin{figure}[htb!]
\centering%
\includegraphics[scale = 0.5]{Davidson.pdf}
\caption{Davidson Fraser Model of Compilation\cite{Davidson}}
\label{fig:FigureDavidson}
\end{figure}


As seen from figure \ref{fig:FigureDavidson}, the front end here converts the source code into an abstract machine code. The abstract machine
 code is machine independent. The
expander converts the abstract machine code to a set of register transfers. The expander is so named
because it takes a single input instruction and converts it into a sequence of register transfers. Register transfer is an intermediate
representation that is machine dependent. It gets its machine dependent parameters from machine description files.
 Since the expander is followed
by the Cacher, which is an optimizer that acts on register transfers, the expander can be written in a simple way so that it outputs a naive 
sequence of instructions. The combiner's work is to combine a sequence of register transfer instructions and produce 
a single instruction wherever possible. The assigner finally produces the assembly code.


Here the cacher is machine independent, though it works on register transfers which is a machine dependent code. 
This is because of the fact 
that the register transfers are machine specific but their form is machine independent\cite{Davidson}. The cacher takes advantage of this
fact and works on the form of the register transfers.
This object code optimizer makes it possible to write a simple expander, 
which need not produce an efficient code and only has to produce the correct code. Retargeting involves rewriting the expander and the
assigner, which are easy tasks since both use simple algorithms.

 
\section{GCC's Model}
GCC's compilation model is a modified version of the Davidson Fraser compilation model. The various phases in its compilation
process can be split into three phases\cite{gccwiki},

\begin{itemize}
 \item Front end
 \item Target independent code transformations
 \item Code generation
\end{itemize}

\begin{figure}[htb!]
\centering%
\includegraphics[scale = 0.5]{GCC.pdf}
\caption{GCC's Model of Compilation}
\label{fig:FigureGCC}
\end{figure}

Like in the Davidson Fraser Model, the front end here transforms the source code to a machine independent representation, GIMPLE.
The second phase, performs several SSA based optimizations on the GIMPLE code, then performs expansion, i.e., conversion of GIMPLE
code to what is called the non-strict Register Transfer Language(RTL). The non-strict RTLs are so named because, in the second phase of compilation,
the RTL patterns matched from constructs like {\em define\_insn}s are matched without their corresponding operand 
{\em constraints} being satisfied. Finally optimizations are performed over this RTL and given to the next phase. The code generation phase 
converts the non-strict RTL to strict RTL (unlike non-strict RTL, in strict RTL it is made sure that the patterns that match also satisfies all the
operand constraints), schedules instructions , performs peephole optimizations and finally generates assembly code.  

The machine description files are used in  expansion and code generation operations. In the phase where the expand operation
is done, the RTL templates from the named define\_insns and define\_expands are used. In the code generation phase, where the
strict RTLs are converted to assembly code, the names are ignored and the define\_insn which contains the current RTL pattern as
its template is matched and the corresponding assembly code is emitted. 

\section{GCC's Back End Organization}
 A back end for a target {\tt machine} in GCC must contain the following files and directories apart from other files which are not of 
interest now,
\begin{enumerate}
 \item A directory named {\tt machine} under gcc/config and the following files under this directory {\tt machine}.
\item A file named {\tt machine}.md.
\item A file named {\tt machine}.c.
\item A header file {\tt machine}.h and {\tt machine}-protos.h.
\end{enumerate}

The file {\tt machine}.md contains a list of instruction patterns that the machine supports. The header file {\tt machine}.h, contains
macros which describes the machine's properties and which could not be included in the {\tt machine}.md file. The source file
{\tt machine}.c contains a variable targetm, which 	is a structure with pointers to datastructures and functions that are related to
the target machine. Also it must contain definitions of the datastructures and functions that are not defined elsewhere.




The machine description file contains a set of expressions of the form {\tt define\_$\ast$}. They are {\tt define\_insn},  
{\tt define\_peephole}, {\tt define\_split}, {\tt define\_insn\_and\_split}, {\tt define\_peephole2}, {\tt define\_expand}, {\tt define\_delay},   
{\tt define\_asm\_attributes}, \\ 
{\tt define\_cond\_exec}, {\tt define\_predicate}, {\tt define\_special\_predicate}, \\
{\tt define\_register\_constraint}, {\tt define\_constraint}, {\tt define\_memory\_constraint}, {\tt define\_address\_constraint}, 
{\tt define\_cpu\_unit}, {\tt define\_query\_cpu\_unit}, \\
{\tt define\_bypass}, {\tt define\_automaton}, {\tt define\_reservation}, \\ {\tt define\_insn\_reservation}, {\tt define\_attr} and {\tt define\_enum\_attr}.
 

                  

Here we are interested in those expressions which as part of their format have RTL templates to match with. So the list above
shrinks to

\begin{itemize}
 \item define\_insn
 \item define\_peephole
 \item define\_split
 \item define\_insn\_and\_split
 \item define\_peephole2
 \item define\_expand
  \end{itemize}


\subsection{RTL Expression Codes}
The RTL templates in these expressions tell which instructions match these patterns and also how the operands can be 
found\cite{gccint}. The current work involves parsing this RTL template and extracting out patterns from them, which can be 
instantiated with parameters. RTL uses five different types of objects, viz., expressions, integers, wide integers, strings and
vectors. Among the five listed above, expressions are of interest to us. The gcc internals documentation provides a good
description of RTL expressions and also the file rtl.def from the GCC source lists all the possible expressions. Each RTL expression
has an expression code(RTX code) associated with it. The RTX code is machine independent. The RTX code gives information like,
how many operands the expression contains and what are the types of each operand.

The RTX codes are grouped into classes based on the type of operation, operands. For example, the class RTX\_COMM\_ARITH, contains 
all the RTX codes which perform commutative binary operations like PLUS, AND, etc. The file rtl.def contains a series of
DEF\_RTL\_EXPR() macro statements, each of which defines an RTL expression. The macro has four operands, 

\begin{enumerate}
 \item The internal name of the RTX.
 \item The name of the RTX in ASCII format.
 \item The print format of the RTX.
 \item The class of the RTX.
\end{enumerate}



The third operand is a sequence of characters called the format. This format enumerates the number of objects that the RTL 
expression contains and the type of each of the objects. For example, the format for define\_insn is sEsTV. Each character in a 
format has a particular meaning. The meaning of some of the most used format characters are listed below,
\begin{description}
 \item s - A string.
 \item e - An RTL expression.
 \item i - An integer.
 \item E - A vector of RTL expressions.
 \item V - This is same as E, but this object is optional.
 \item T - This is like strings, but treated speacially by rtl\_reader used internally by gcc.
\end{description}

The format of the define\_insn expression can be listed as below.\\ 
% \begin{center}
(define\_insn string\\
\indent       [RTL Expression Vector]\\
\indent       string\\
\indent       string\\
\indent       [Optional RTL Expression Vector]\\
)\\ 
% \end{center}



From the above list, it is understood that, define\_insn(format is sESTV, as stated above) has a string, followed by an RTL expression 
vector, then
two strings and finally an optional RTL expression vector. This is explained in more detail in the subsequent section. In summary, the 
file rtl.def, gives the syntax of each RTL expression while the semantics can be understood from the comments in rtl.def and GCC's documentation\cite{gccint}.

\section{Standard Pattern Names}

Names are given to patterns defined by define\_expand expressions and optionally to define\_insn expressions also. Two different
patterns can not use the same names i.e., the names are unique. GCC provides a set of standard pattern names, whose semantics are well defined and is used
in the RTL generation phase. If the name matches a standard pattern name, gcc calls the function gen\_name implicitly that
generates the RTL pattern for that name. Names can start with a *, so that they can be traced in debugging operations, as such names can
be easily traced in RTL dumps while debugging. Such names
won't be used in RTL generation phase. 


\section{RTL Templates}


An RTL template is a vector of incomplete rtl expressions, as it contains a number of unresolved operands which have to be
resolved by expressions like match\_operand, match\_dup, etc. If the vector has only one RTL expression, then that expression is the 
template of the instruction pattern. 
If the vector has multiple expressions, then it is as though there is a \emph{parallel} construct that executes all the expressions in parallel.
An RTL template tells which instructions match the particular 
pattern and how to find its operands. For a named pattern, it also
tells how to construct the instruction from the operands. To construct an instruction, the operands must be substituted into a
copy of the template. An RTL template uses rtl expressions like match\_operand, match\_dup, match\_operator,etc. Let us look
at the format of a match\_operand expressions
\begin{verbatim}
(match_operand:m n predicate constraint) 
\end{verbatim}

This expression acts as a placeholder for the operand number 'n' of the instruction. If an instruction is being constructed,
the operand number 'n' will be substituted here. If an instruction is being matched, the operand appearing at this position must 
satisfy the predicate mentioned, else the instruction won't be matched. Predicate is a string that is a name of a function that
accepts two arguments, an expression and the machine mode 'm'. If the predicate is empty, then no tests need to be done. 
Constraints allows a more detailed selection after the operand satisfies the predicate condition. Constraints can be used to 
decide on reloading and the register class choices. The operand numbers are numbered from zero. For example, let us look at the following match\_operand expression,

\begin{example}
\begin{verbatim}
(match_operand:SI 0 ``register_operand'' ''r'')
\end{verbatim}
\end{example}


This expression will try to match operand zero with machine mode Single Integer mode(SI). The predicate function to be used is 
{\tt register\_operand} and the constraint to be tested is {\tt r}. The constraint here means that the operand must be a register and it
must be one of the general registers.

 Now let us look at the define\_$\ast$ expressions
which have RTL expressions in them and see how they are used. 

\subsection{define\_insn Expression}

 The define\_insn expression is
very important because this describes an instruction pattern. Let us look at what constitutes a define\_insn expression and the
meaning of each of its constituents. A define\_insn expression contains,
\begin{enumerate}
 \item An optional name. If the name is present, and if this matches one of the standard names that the compiler is aware of,
this define\_insn will be used in the RTL generation phase. If the name is not present or if the name is not a known name, then
this define\_insn will not be used in the RTL generation phase, but can be used in other phases.
\item An RTL template. This is same as the RTL template that was discussed in the previous section.
\item A condition. This is a C expression, which is the final test to be performed to decide whether the instruction body matches this pattern.
\item The output template. This is a string that says how to output the assembly code for the matching instructions.
\item An optional vector of attributes. 
\end{enumerate}

A sample define\_insn expression is listed below.

\begin{example}
\onehalfspacing
 \begin{verbatim}
  (define_insn "add<mode>3"
  [(set (match_operand:ANYF 0 "register_operand" "=f")
	(plus:ANYF (match_operand:ANYF 1 "register_operand" "f")
		   (match_operand:ANYF 2 "register_operand" "f")))]
  ""
  "add.<fmt>\t%0,%1,%2"
  [(set_attr "type" "fadd")
   (set_attr "mode" "<UNITMODE>")])
 \end{verbatim}

\end{example}


\subsection{define\_expand Expression}

A define\_expand expression looks similar to a define\_insn expression, but the former is used only in the RTL generation phase and it can produce 
more than one RTL instruction. The RTL instruction generated by a define\_expand expression must match the RTL template of some define\_insn expression.
Otherwise, the compiler will crash when trying to generate code or during optimization. A define\_expand expression contains,

\begin{enumerate}
 \item A name. In a define\_expand expression, the name is not optional, as in the case of a define\_insn expression.
 \item An RTL Template. The RTL template here has one different meaning. If the RTL template has more than one RTL expression, then it is not
 assumed that there is an implicit PARALLEL surrounding them.
 \item A condition. This is same as in the define\_insn expression, but the condition here depends more on the machine specific flags.
 \item Preparatory statements. This is a string containing a set of C statements, which has to executed before the RTL code is emitted.
\end{enumerate}

A sample define\_expand expression is listed below.

\begin{example}
\onehalfspacing
 \begin{verbatim}
  (define_expand "mul<mode>3"
  [(set (match_operand:GPR 0 "register_operand")
	(mult:GPR (match_operand:GPR 1 "register_operand")
		  (match_operand:GPR 2 "register_operand")))]
  ""
{
  if (TARGET_LOONGSON_2EF || TARGET_LOONGSON_3A)
    emit_insn (gen_mul<mode>3_mul3_loongson (operands[0], 
                             operands[1], operands[2]));
  else if (ISA_HAS_<D>MUL3)
    emit_insn (gen_mul<mode>3_mul3 (operands[0], 
                              operands[1], operands[2]));
  else if (TARGET_FIX_R4000)
    emit_insn (gen_mul<mode>3_r4000 (operands[0], 
                              operands[1], operands[2]));
  else
    emit_insn
      (gen_mul<mode>3_internal (operands[0], 
                              operands[1], operands[2]));
  DONE;
})
 \end{verbatim}

\end{example}


\subsection{define\_split Expression}
A define\_split expression tells the compiler how to split a complex instruction into two or more simpler instructions. This splitting is necessiated
under two circumstances. One is the case, where the machine may have instructions that require delay slots in between. The second case is,
the output of some instructions won't be available for multiple cycles. In both these cases, the optimization phase of the compiler needs the ability
to place instructions in slots that are empty. This is supported by the define\_split expression. A define\_split expression contains,

\begin{enumerate}
 \item An instruction pattern(RTL Template). This is the pattern that is to be split.
 \item A condition. The condition here is same as in a define\_insn expresion.
 \item Output instructions. This is a list of instruction patterns that will be generated. That is the input instruction pattern is split into a list
 of instructions given by this output instructions.
 \item Preparatory statements. This is similar to those in a define\_expand expression. 
\end{enumerate}


A sample define\_split expression is listed below.

\begin{example}
\onehalfspacing
 \begin{verbatim}
(define_split
  [(set (match_operand:GPR 0 "d_operand")
	(const:GPR (unspec:GPR [(const_int 0)] UNSPEC_GP)))]
  "TARGET_MIPS16 && TARGET_USE_GOT && reload_completed"
  [(set (match_dup 0) (match_dup 1))]
  { operands[1] = pic_offset_table_rtx; })  
 \end{verbatim}
\end{example}


\subsection{define\_insn\_and\_split Expression}
This is used, when the instruction pattern of a define\_split expression matches exactly with that of a define\_insn expression. So this expression
contains all the fields from the define\_insn expression and define\_split expression. This will have two separate conditions, one for instruction
splitting and another for instruction matching (used in define\_insn).

A sample define\_insn\_and\_split expression is listed below.

\begin{example}
\onehalfspacing
\begin{verbatim}
 (define_insn_and_split "loadgp_newabi_<mode>"
  [(set (match_operand:P 0 "register_operand" "=d")
	(unspec:P [(match_operand:P 1)
		   (match_operand:P 2 "register_operand" "d")]
		  UNSPEC_LOADGP))]
  "mips_current_loadgp_style () == LOADGP_NEWABI"
  { return mips_must_initialize_gp_p () ? "#" : ""; }
  "&& mips_must_initialize_gp_p ()"
  [(set (match_dup 0) (match_dup 3))
   (set (match_dup 0) (match_dup 4))
   (set (match_dup 0) (match_dup 5))]
{
  operands[3] = gen_rtx_HIGH (Pmode, operands[1]);
  operands[4] = gen_rtx_PLUS (Pmode, operands[0], operands[2]);
  operands[5] = gen_rtx_LO_SUM (Pmode, operands[0], operands[1]);
}
  [(set_attr "type" "ghost")])
\end{verbatim}
 
\end{example}


\subsection{define\_peephole Expression}
The use of this expression is deprecated.

\subsection{define\_peephole2 Expression}

Peephole optimizations are done after the register allocation phase but before the instruction scheduling phase. The format of this expression is almost
similar to the define\_split expression except that the instruction pattern to be matched in this case is a sequence of instructions instead of a single
instruction.  This also tells, what additional scratch registers are required(if any) and their lifetimes.

A sample define\_peephole2 expression is listed below.

\begin{example}
\onehalfspacing
\begin{verbatim}
 (define_peephole2
  [(parallel
       [(set (match_operand:SI 0 "lo_operand")
	     (match_operand:SI 1 "macc_msac_operand"))
	(clobber (scratch:SI))])
   (set (match_operand:SI 2 "d_operand")
	(match_dup 0))]
  ""
  [(parallel [(set (match_dup 0)
		   (match_dup 1))
	      (set (match_dup 2)
		   (match_dup 1))])])
\end{verbatim}
 
\end{example}




   
